package com.zhangxiaofanfan.hotcode.fourth.third;


import java.util.ArrayList;
import java.util.List;

/**
 * TODO
 *
 * @author zhangxiaofanfan
 * @date 2024-06-26 20:33:33
 */
public class HotCode057 {
    public static void main(String[] args) {
        HotCode057 hotCode057 = new HotCode057();
        System.out.println(hotCode057.letterCombinations("23"));

    }

    private final char[][] keys = new char[][] {
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'},
    };

    List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) {
            return result;
        }
        result.add("");
        bfs(digits, 0);
        return result;
    }

    public void bfs(String digits, int index) {
        if (index >= digits.length()) {
            return;
        }
        int count = result.size();
        for (int i = 0, j; i < count; i++) {
            String first = result.removeFirst();
            for (j = 0; j < keys[digits.charAt(index) - '2'].length; j++) {
                result.addLast(first + keys[digits.charAt(index) - '2'][j]);
            }
        }
        bfs(digits, index + 1);
    }
}
